#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <stack>
#include "TGPolygon.h"

void TGPolygon::init() {
    std::vector<TGPoint>().swap(data);
}

void TGPolygon::add(const TGPoint& p) {
    data.emplace_back(p);
}

TGPolygon& TGPolygon::operator = (const TGPolygon& src) {
    data = src.data;
    return *this;
}

double TGPolygon::getArea() {
    double ans = 0;
    int n = data.size();
    // for(int i = 0; i < n-1; i ++) {
    //     ans += xmul(data[i], data[i+1]);
    // }
    // ans += xmul(data[n-1], data[0]);

    for(int i = 1; i < n-1; i ++) {
        ans += (data[i]-data[0]) ^ (data[i+1]-data[0]);
    }
    ans = fabs(ans);
    return ans/2;
}

TGPoint TGPolygon::getCenter() {
    int n = data.size();
    TGPoint center;
    center.x = 0.0; center.y = 0.0;
    for(auto& p : data) {
        center.x += p.x;
        center.y += p.y;
    }
    if(n == 0) return center;
    center.x /= n; center.y /= n;
    return center;
}

void polarAngleSortWithAtan2(TGPolygon& polygon) {
    TGPoint center = polygon.getCenter();
    std::sort(polygon.data.begin(), polygon.data.end(),[&](TGPoint& p1, TGPoint& p2){
        double d1 = atan2(p1.y-center.y, p1.x-center.x);
        double d2 = atan2(p2.y-center.y, p2.x-center.x);
        if(d1 != d2) {
            return d1 < d2;
        }
        else {
            return p1 < p2;
        }
    });
}

void polarAngleSortWithCross(TGPolygon& polygon) {
    TGPoint center = polygon.getCenter();
    std::sort(polygon.data.begin(), polygon.data.end(),[&](TGPoint& p1, TGPoint& p2){
        double d = xmul(p1-center, p2-center);
        if(d == 0.0) {
            return p1 < p2;
        }
        else {
            return d > 0;
        }
    });
}


bool TGPolygon::isContainPoint(const TGPoint& p) const{
    int n = data.size();
    /*
    利用向量叉乘判断点是否在多边形内
    若点p在多边形内部，对于多边形定点i,逆时针相邻点i+1来说，
    其叉积<i_i+1,i_p> 大于0在内部，小于0在外部，等于0在边上
    */
    // TGPoint p1, p2;
    // for(int i = 0; i < n-1; i ++) {
    //     p1 = data[i+1] - data[i];
    //     p2 = p - data[i];
    //     if(xmul(p1, p2) < 0) {
    //         return false;
    //     }
    // }
    // p1 = data[0] - data[n-1];
    // p2 = p - data[n-1];
    // if(xmul(p1, p2) < 0) {
    //     return false;
    // }
    // return true;    


    //利用射线法判断是否相交，即从点p一条向右的射线，然后计算穿过多边形的边数，偶数则在外部，奇数则在内部
    int i, j;
    bool c = false;
    for(i = 0; i < n; i++) {
        j = (i+1) % n;
        auto& p1 = data[i], &p2 = data[j];
        //点p位于多边形边ij上
        if(commonLine({data[i], data[j]}, p) && isColinePointOnSegment({data[i], data[j]}, p)) {
            return true;
        }

        if(p1.y == p2.y) continue;
        if(p.y < std::min(p1.y, p2.y)) continue;
        if(p.y >= std::max(p1.y, p2.y)) continue;
        //(data[i].y > p.y)!=(data[j].y > p.y) &&
        if( 
            ( p.x < (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x )
        ) {
            c = !c;
        }
    }
    return c;
}

void getEdge(const TGPolygon& polygon, int n, TGLine& line) {
    if(n == polygon.data.size()-1) {
        line = TGLine(polygon.data[n], polygon.data[0]);
    }
    else {
        line = TGLine(polygon.data[n], polygon.data[n+1]);
    }
}

void getIntersectionPoints(TGPolygon& polygon1, TGPolygon& polygon2, TGPolygon& polygon3) {
    int n = polygon1.data.size(), m = polygon2.data.size();
    TGPoint p;
    TGLine e1, e2;
    for(int i = 0; i < n ; i++) {
        getEdge(polygon1, i, e1);
        for(int j = 0; j < m; j ++) {
            getEdge(polygon2, j, e2);
            if(intersection(e1, e2, p)) {
                polygon3.add(p);
            }
        }
    }
}

void getAllIntersectionPoints(TGPolygon& polygon1, TGPolygon& polygon2, TGPolygon& polygon3) {

    polygon3.init();

    //将多边形1和2互相包含的点添加到多边形3中
    for(auto& p : polygon1.data) {
        if(polygon2.isContainPoint(p)) {
            polygon3.add(p);
        }
    }
    for(auto& p : polygon2.data) {
        if(polygon1.isContainPoint(p)) {
            polygon3.add(p);
        }
    }
    
    //将多边形1和2交叉的点添加到多边形3中
    getIntersectionPoints(polygon1, polygon2, polygon3);

    //将得到的多边形按极角逆序排序并去重
    polarAngleSortWithAtan2(polygon3);
}

void antiClockwiseAndRemoveDuplicate(TGPolygon& polygon) {

    //利用atan2完成极角排序
    polarAngleSortWithAtan2(polygon);


    //然后逆时针遍历顶点去除重复点
    TGPolygon p1;
    int n = polygon.data.size();
    p1.data.push_back(polygon.data[0]);
    for(int i = 1; i < n; i ++) {
        if(equal(polygon.data[i], polygon.data[i-1])) {
            continue;
        }
        p1.data.push_back(polygon.data[i]);
    }

    polygon.data = p1.data;
}


void clipStep(TGPolygon& src, const TGLine& l1) {
    int n = src.data.size();
    TGPolygon tmpPolygon;
    for(int i = 0; i < n; i ++) {
        int j = (i+1) % n;
        const double &xi = src.data[i].x, &yi = src.data[i].y;
        const double &xj = src.data[j].x, &yj = src.data[j].y;
        //计算点i,j关于clip line的方向
        double i_dir = (l1.data.second-l1.data.first)^(src.data[i]-l1.data.first);
        double j_dir = (l1.data.second-l1.data.first)^(src.data[j]-l1.data.first);
        // std::cout << "方向" << i_dir << " " << j_dir << "\n";
        if(i_dir < 0 && j_dir < 0) {
            //两点都在内部，选取第二个点
            // std::cout << xj << " " << yj << "\n";
            tmpPolygon.add({xj, yj});
        }
        else if(i_dir >= 0 && j_dir < 0) {
            //当点i在外部，点j在内部时， 添加点j以及线段ij和线段l1的交点
            TGPoint p;
            // std::cout << "当前线段" << xi << " " << yi << " " << xj << " " << yj << "\n";
            if(lineIntersect({xi, yi, xj, yj}, l1, p)) {
                tmpPolygon.add(p);
                // std::cout << p.x << " " << p.y << "\n";
            }
            tmpPolygon.add(src.data[j]);
            // std::cout << xj << " " << yj << "\n";
        }
        else if(i_dir < 0 && j_dir >= 0) {
            // 当点i在内部，j在外部时，添加线段ij和线段l1的交点
            TGPoint p;
            if(lineIntersect({xi, yi, xj, yj}, l1, p)) {
                tmpPolygon.add(p);
                // std::cout << p.x << " " << p.y << "\n";
            }
        }
    }
    // std::cout << tmpPolygon.data.size() << "\n";
    src = tmpPolygon;
}

void SHClip(TGPolygon& src, TGPolygon& clipper, TGPolygon& dst) {

    /*
    由于该算法默认是顺时针而我们默认是逆时针,因此需要逆序一下
    该算法求解两多边形相交问题的缺点：
    1.该算法需要较大的内存空间
    2.对两个多边形的输入顺序有要求
    */

    std::reverse(src.data.begin(), src.data.end());
    std::reverse(clipper.data.begin(), clipper.data.end());

    dst.init();
    dst = src;
    int n = clipper.data.size();
    for(int i = 0; i < n; i ++) {
        int j = (i+1) % n;
        clipStep(dst, {clipper.data[i], clipper.data[j]});
        // std::cout << "-------------\n";
        // for(auto& p : dst.data) {
        //     std::cout << p.x << " " << p.y << std::endl;
        // }
        // std::cout << "-------------\n";
    }

    // antiClockwiseAndRemoveDuplicate(dst);

    //处理结束，将原来多边形再次逆序
    std::reverse(src.data.begin(), src.data.end());
    std::reverse(clipper.data.begin(), clipper.data.end());
}


bool findConvexHullWithGraham(std::vector<TGPoint>& points, TGPolygon& polygon) {
    int n = points.size();
    // std::cout << n << std::endl;
    if(n < 3) {
        return false;
    }
    else if(n == 3) {
        polygon.data = points;
        return true;
    }
    polygon.init();
    std::vector<TGPoint>S;
    //第一步，找到纵坐标最小的点为起点,如果有多个纵坐标相同的选取x坐标值最小的，记该点为凸包起点
    int idx = 0;
    for(int i = 1; i < n; i ++) {
        if(points[i].y < points[idx].y) {
            idx = i;
        }
        else if(dcmp(points[i].y, points[idx].y) == 0) {
            if(points[i].x < points[idx].x) {
                idx = i;
            }
        }
    }
    //为了后续处理方便，将凸包起点和0号点交换
    std::swap(points[0], points[idx]);

    //以凸包起点为原点，将剩余点进行极角排序，如果极角相同则按照距离凸包起点距离排序
    std::sort(points.begin()+1, points.end(), [&](TGPoint& p1, TGPoint& p2){
        double d1 = (p1-points[0]) ^ (p2-points[0]);
        int flag = dcmp(d1, 0.0);
        if(flag == 0) {
            double d2 = (p1-points[0]) * (p1-points[0]);
            double d3 = (p2-points[0]) * (p2-points[0]);
            return d2 <= d3;
        }
        else {
            return flag > 0;
        }
    });

    //依次判断当前点是否可以作为凸包定点
    S.emplace_back(points[0]);
    S.emplace_back(points[1]);
    S.emplace_back(points[2]);
    int top = 2;
    for(int i = 3; i < n; i ++) {
        
        //如果当前点位于之前线段外部，则栈顶元素不可能作为凸包顶点(对于凸包，点集中所有点都应位于凸包边的内部)，弹出栈顶元素。
        //共线元素则选择距离起点最远的即下标最大的，因此当共线时，也选择弹出当前栈顶元素
        while(top > 0 && dcmp((S[top]-S[top-1]) ^ (points[i] - S[top-1]), 0.0) <= 0) {
            top --;
            S.pop_back();
        }
        S.emplace_back(points[i]);
        top ++;
    }

    polygon.data = S;
    return true;
}


std::vector<TGPoint> mincowskySum(const TGPolygon& polygon1, const TGPolygon& polygon2) {
    std::vector<TGPoint> ret;
    TGPoint p1, p2;
    int n = polygon1.data.size(), m = polygon2.data.size();
    int i = 0, j = 0;
    // printf("%d %d %d\n", n, m, n+m);
    // printf("%d\n", ret.size());
    ret.reserve(n+m);
    ret.emplace_back(polygon1.data[i] + polygon2.data[j]);
    //std::cout << ret.back().x << " " << ret.back().y << std::endl;

    while(i < n && j < m) {
        // printf("......\n");
        //printf("%d\n", ret.size());
        p1 = polygon1.data[(i+1)%n] - polygon1.data[i];
        p2 = polygon2.data[(j+1)%m] - polygon2.data[j];
        if(dcmp(p1^p2) >= 0) {
            ret.emplace_back(ret.back() + p1);
            i ++; 
        }
        else {
            ret.emplace_back(ret.back() + p2);
            j ++;
        }
    }
    //printf("%d %d\n", j, m);
    while(i < n) {
        // printf(".....");
        p1 = polygon1.data[(i+1)%n] - polygon1.data[i];
        ret.emplace_back(ret.back() + p1);
        i ++;
    }
    //printf("1123\n");
    while(j < m) {
        // printf(".....123\n");
        p2 = polygon2.data[(j+1)%m] - polygon2.data[j];
        ret.emplace_back(ret.back() + p2);
        j++;
    }
    //printf("final\n");
    return ret;
}